All Questions
10 questions
0votes
0answers
49views
Min cost perfect matching, but with conflicting edge pairs
Consider the following variant of min-weight perfect matching. We are given a graph $G = (V,E)$ with non-negative weights on the edges. We are also given a collection of pairs of edges $P \subseteq E \...
- 649
1vote
0answers
60views
Find the minimum cost spider joining a root to some leaves
A spider is a tree with at most one vertex of degree greater than 2. This vertex is called the head of the spider. I am interested in the following problem: We are given an undirected graph $G = (V,E)$...
- 649
3votes
2answers
424views
What is the best approximation and exact algorithm for vertex cover on cubic graphs?
"Best" = best performing in terms of run-time for exact algorithm and approximation ratio for an approximation algorithm.
- 41
1vote
0answers
50views
Sparse coding and matching pursuit algorithms
Is it true that all known sparse coding algorithms which work efficiently in practice don't have convergence proofs and always use an intermediate step of a matching/subspace pursuit algorithm on the ...
- 1,463
5votes
2answers
199views
Solution/Hardness of the following (integer) budgeted problem?
I have no idea how to solve the following INTEGER problem or prove its hardness. Thanks for any help/comment/open discussion! Assume there are $N$ startups. For each startup $i$, you can invest $x_i\...
- 119
0votes
0answers
33views
On approx-preserving P- and A-reducibilities
Let $X$ and $Y$ be two NPO problems. Let $(f,g)$ be a reduction between $X$ and $Y$, in particular, assume that $(f,g)$ is both P-reduction and A-reduction, i.e., there exist two poly-time ...
- 650
11votes
1answer
253views
maximize MST(G[S]) over all induced subgraphs G[S] in a metric graph
Has this problem been studied before? Given a metric undirected graph G (edge lengths satisfy triangle inequality), find a set S of vertices such that MST(G[S]) is maximized, where MST(G[S]) is the ...
- 769
2votes
0answers
71views
Small area containing large amount of patterns
The problem: I come across a theoretical problem when designing characters for electron-Beam lithography. Abstractly, given an integer $m$, let $\mathcal{M}$ be the set of $(0,1)$-matrix $A_{p\times ...
- 21
9votes
2answers
3kviews
What are good approximation algorithms for the subset sum problem so far?
By "good", I mean either the algorithm provides a relatively tight bound or it has a relatively fast running time. Any reference is welcome.
- 467
4votes
1answer
575views
Better approximation for special case of 3-hitting set
I have a question based on 3-Hitting Set problem. In this problem, we are given a universal set U of size n and a set of subsets S such that $\forall $ s $\in$ S |s|<=3. FOr this problem, Integer ...
- 467
